/**
 *  LinkedList
 *
 *  Append forward
 *
 */

public class LinkedList<E extends Comparable<E>> {
    
    private class Node {
        private E item;
        private Node next;
    }

    public Node head = null;
    private int total;

    public Node add(E item) {
        Node current = head;

        head = new Node();
        head.item = item;
        head.next = current;
        total++;

        return head;
    }

    public void reverseI() {
        if (head == null || head.next == null) {
            return;
        }

        Node prev = null;
        Node curr = head;
        Node next;
        
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        head = prev;
    }

    public Node reverseR(Node node) {
        // Base case
        if (node == null) {
            return null;
        } else if (node.next == null) {
            head = node;
            return node;
        }
        
        Node tail = reverseR(node.next);
        tail.next = node;
        node.next = null;

        return node;
    }

    public void reverseInsert() {
        if (head == null || head.next == null) {
            return;
        }

        Node tail = head.next;

        while (tail.next != null) {
            Node next = tail.next;
            tail.next = next.next;
            next.next = head.next;
            head.next = next;
        }

        Node curr = head;
        tail.next = curr;
        head = head.next;
        curr.next = null;
    }

    public int size() {
        return total;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        Node p = head;
        while (p != null) {
            sb.append(p.item.toString()).append(" ");
            p = p.next;
        }

        return sb.toString();
    }

}
